#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>
#include <math.h>
#include <limits.h>
#define LOCAL_TEST 0
#define M 0

/*
 * m^n
 */
static int power(int m, int n){
	if(n==0) return 1;
	if(n%2) return power(m, n-1) * m;
	else {
		int x = power(m, n/2);
		return x * x;
	}
}

static int power2(int m, int n){
	int ans, s;
	for(ans=1, s=m; n; n>>=1){
		if(n &1)ans *= s;
		s *= s;
	}
	return ans;
}

static int power3(int m, int n){
	int stack[68];
	int i, j, ans;
	for(i=0, j=n; j; ++i){
		stack[i] = j;
		if(j&1) --j;
		else j >>=1;
	}
	for(ans=1, --i; i>=0; --i){
		if(stack[i] & 1) ans *=m;
		else ans *= ans;
	}
	return ans;
}
static void solve(void){
	int i, m, n;
	for(i=0; i<5; ++i){
		m = rand()%10 + 1;
		n = rand()%8;
		printf("%d^%d = %d, %d, %d\n", m, n, power(m, n), power2(m, n), power3(m, n));
	}
}

#if LOCAL_TEST
void run(void){
		solve();
}
#endif
